package edu.siu.math.egut.util;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
import java.util.regex.Pattern;

import org.apache.commons.collections15.BidiMap;
import org.apache.commons.collections15.bidimap.DualHashBidiMap;

import edu.siu.math.egut.local.SectionIntegral.UnipotentPrefixPair;
import edu.siu.math.egut.main.OutputStyle;

/**
 * The Class Unipotent models certain unipotent elements of split
 * connected reductive algebraic groups. Let G be such a group and assume that G
 * is equipped with a choice of maximal torus T, used to define roots. Let U be
 * a maximal unipotent subgroup of G which is compatible with T. Any element of
 * U can be written as a product of elements of the form x_a(r) where, for a
 * root a, x_a is an isomorphism between the one-dimensional unipotent subgroup
 * associated to a and the additive group-scheme. Such elements are called
 * "simple unipotents," or sunipotents for short. A unipotent is represented
 * simply as a product of sunipotents. Because not every word in the sunipotents
 * corresponds to a unipotent element of G, it is possible to define objects of
 * class Unipotent which are not, actually, unipotent. Some checking is done to
 * guard against this, but a certain amount of care and/or exception-handling on
 * the users part will be required.
 * 
 * 
 * @author Joe Pleso
 * @author Joseph Hundley
 * 
 */
public class Unipotent implements Serializable{

    public static class PrefixRootPair {
	private final String prefix;
	private final int[] root;
	public String getPrefix() {
	    return prefix;
	}
	public PrefixRootPair(String prefix, int[] root) {
	    super();

	    this.prefix = prefix;
	    this.root = root;
	}
	public int[] getRoot() {
	    return root;
	}

    }
    /**
     * @author josephhundley
     *
     */
    public enum InputStyle {
	/**
	 * The "style" for any input which can not be parsed.
	 */
	NONSENSE, 
	/**
	 * An input style for inputing unipotent elements:  a list of roots
	 * followed by a string "prefix."   
	 */
	ROOTS_PLUS_STRING

    }
    private static final long serialVersionUID = 517L;
    private static final char[] DROP_ROOT_MENU_OPTIONS = {'K','k','S','s','C','c'};
    private static final Pattern ROOTS_PLUS_STRING_PATTERN 
    = Pattern.compile("unipotent\\s*roots\\s*\\[\\s*(\\[(\\d,\\s*)*\\d\\s*\\],?\\s*)*\\]\\s*prefix.*",
	    Pattern.CASE_INSENSITIVE);
    /**
     * The pattern matched by "default" variables.  
     * (E.g., those created by  the int[][], String Constructor.)
     */
    public static final Pattern DEFAULT_VARIABLE_PATTERN = Pattern.compile(".*_\\{-?\\d\\d+\\}");
    private static final int PAGE_WIDTH = edu.siu.math.egut.io.Constants.PAGE_WIDTH;
    
    /**
     * Multiply two Unipotents together. The Unipotents must be from the same
     * group.
     * 
     * @param a the first Unipotent to be multiplied
     * @param b the second Unipotent to be multiplied
     * @return the product ab of Unipotents a and b, with all associations 
     * of a preserved, and associations of b preserved iff they are 
     * consistent with those of a.
     * 
     */
/* 
 * WARNING: This method will create Unis in which all Sunis are 
 * immobile.
 */
    
    public static Unipotent multiply(Unipotent a, Unipotent b) {
	if (a.getGroup() != b.getGroup()) {
	    throw new IllegalArgumentException();
	}

	List<Sunipotent> list = new ArrayList<Sunipotent>();
	list.addAll(a.product);
	list.addAll(b.product);
	
	Unipotent c =  new Unipotent(a.getGroup(), list);
	for( Sunipotent s: a.associations.keySet())
	{
	    c.associate(s, a.associations.get(s));
	}
	for( Sunipotent s: b.associations.keySet())
	{
	    if( !c.associations.containsValue(b.associations.get(s)))
	    c.associate(s, b.associations.get(s));
	}
	
	return c;

    }
    /**
     * Multiply a Unipotent by a Sunipotent (on the right). The Unipotents must be from the same
     * root system.
     * 
     * @param u  Unipotent 
     * @param s  Sunipotent 
     * @return the product u.s of u and s, as a Unipotent object with all associations 
     * of u preserved, no association assigned to s.
     * 
     */
/* 
 * WARNING: This method will create Unis in which all Sunis are 
 * immobile.
 */
    
    public static Unipotent times(Unipotent u, Sunipotent s) {
	if (u.getGroup().getRank() != s.getRoot().length) {
	    throw new IllegalArgumentException();
	}

	List<Sunipotent> list = new ArrayList<Sunipotent>();
	list.addAll(u.product);
	list.add(s);
	
	Unipotent c =  new Unipotent(u.getGroup(), list);
	for( Sunipotent s1: u.associations.keySet())
	{
	    c.associate(s1, u.associations.get(s1));
	}
	
	return c;

    }
   
    /**
     * Modify the current Unipotent by appending the given Sunipotent to it.
     * @param s a Sunipotent
     */
    public void rightMultiply(Sunipotent s){
	if(s.getRoot().length != this.group.getRank()){
	    throw new IllegalArgumentException();
	}
	
	product.add(s);
	
    }
    /**
     * Modify the current Unipotent by appending the given Sunipotent to it.
     * @param s a Sunipotent
     */
    public void leftMultiply(Sunipotent s){
	if(s.getRoot().length != this.group.getRank()){
	    throw new IllegalArgumentException();
	}
	
	product.add(0, s);
	
	
    }
    
    /**
     * Conjugates the unipotent by a word in the standard 
     * representatives for the simple reflections in the 
     * Weyl group.
     * @param weylAsInt an integer, interpreted as a word in the
     * simple reflections, with each digit being an individual 
     * reflection.  An error will result if any of the digits
     * exceeds the rank of the ambient group.
     */
    public void actBy(int weylAsInt){
	
	for(int i = 0 ; i < product.size(); i++){
	    Sunipotent newSuni = get(i).imageUnder(weylAsInt);
	    if(isMobile(i)){
		immobile.remove(get(i));
		immobile.add(newSuni);
	    }
	    if( stringOf(get(i))!=null){
		associate(newSuni, stringOf(get(i)));
	    }
	    product.remove(i);
	    product.add(i,newSuni);
		
	}
	    
	
    }
    
    private final List<Sunipotent> product;
    private final Group group;
    private boolean done;

    private final List<Sunipotent> immobile; 
    // Used in simplification of unipotents.  When two     
    // Unipotents with the same root must be combined, this is     
    // used to determine how and where. 
    
    
    
    private  BidiMap<Sunipotent, String> associations; 
    // Allows the user to associate particular variables    
    // to particular Sunipotents and vice versa.  
    
    

    /**
     * Create a Unipotent that has the form x_{alpha_1}(s1) x_{alpha_2}(s2)...
     * 
     * @param g the Group in which the unipotent lives
     * @param roots a list of roots
     * @param s  a string prefix that will have numbers appended to it
     * @throws NotARootException if any row of roots is not a root of g.
     */
    public Unipotent(Group g, int[][] roots, String s) throws NotARootException {
	group = g;                                      
	List<Sunipotent> list = new ArrayList<Sunipotent>();
	BidiMap<Sunipotent, String> map = 
	    new DualHashBidiMap<Sunipotent, String>();
	for (int i = 0; i < roots.length; i++)
	{
	    String si = defaultString(s,roots[i]);
	    Sunipotent x;
		x = Sunipotent.create(roots[i], Polynomial.create(si));
	    list.add(x);
	    map.put(x, si);
	    
	}
	product = list;
	immobile = new ArrayList<Sunipotent>(list); 
	// all Sunipotents are immobile
	associations = map ; 
	// every Sunipotent owns the variable with which it is initialized.
    }

    /**
     * This method constructs a "default variable" given a string and a root.
     * The idea is that on a large unipotent one might want the 
     * variables to be u_{\alpha_1} \dots u_{\alpha_r}, indexed by the 
     * root in the unipotent, which then appear as subscripts. 
     * 
     * 
     * @param s a string
     * @param is a tuple which should represent a root
     * @return a String representation of s subscripted with is
     */
    public  final static String defaultString(String s, int[] is){
	return s+"_{"+ rootToShortString(is)+"}";
    }
    /**
     * Returns a String representation of the tuple which will be short and 
     * easily readable, provided that the tuple satisfies two properties of roots:
     *  (1) all entries are either nonpositive or nonnegative,
     *  (2) no entry exceeds 9.
     *  This method will not check these properties, much less check that the 
     *  parameter is actually a root of some exceptional group.  However, if
     *  either property fails, the String returned may not look much like a 
     *  short representation of the tuple.
     * @param root should be either "positive" (no negative entries) of "negative" (no positive entries)
     * @return concatenation of all entries if positive, concatenation of absolute values, with a single "-" at the beginning, if negative.
     */
    public  final static String rootToShortString(int[] root) {
	int sign = 1;
	StringBuffer sb = new StringBuffer();
	    for(int i = 0; i < root.length; i++){
		if( root[i] < 0 )
		    sign = -1;
		sb.append((root[i]*sign));
	    }
	    return ((sign == -1)?"-":"")+sb.toString();

	
    }
    /**
     * Creates a new Unipotent with the specified parameters.  
     * 
     * @param g     the group in which this Unipotent lives
     * @param l     the list of Sunipotent factors
     */
    public Unipotent(Group g, List<Sunipotent> l) {
	if (g == null)
	    throw new NullPointerException();

	group = g;
	product = new ArrayList<Sunipotent>(l); 
	immobile = new ArrayList<Sunipotent>(l);
	// by default all Sunipotents are immobile
	associations = new DualHashBidiMap<Sunipotent, String>();
	// no ownerships are created

    }

    /**
     * Constructor which constructs a unipotent from an int[][], which is
     * interpreted as a list of roots, and a String.  
     * 
     * For example if passed the int[][] {{1,1},{2,1},{3,1},{3,2}} and the 
     * String "u", this method creates a Unipotent
     * 
     * x_{[1,1]}(u11) x_{[2,1]}(u21) ... x_{[3,2]} (u32). 
     * 
     * In general, for each root on the list, a Sunipotent is created 
     * which has the specified root and an argument which is a simple 
     * polynomial consisting of a single (String) variable raised 
     * to the first power.  This variable is obtained by appending 
     * a short string representation of the root to the end of 
     * the String argument of this method, which is thus a kind of 
     * "default variable prefix."  
     * 
     * All terms are immobile, each Sunipotent is then associated to the 
     * (unique) variable in its argument.
     * 
     * NOTE 1: If a root appears more than once on our list, then it will produce
     * the same Sunipotent each time that it appears.  (By definition, a Sunipotent
     * is completely determined by its root and argument, so one would not speak of
     * two Sunipotents with the same root and argument, but of the same Sunipotent
     * appearing twice in a product.)
     * 
     * NOTE 2: if an int[][] containing int[]'s which are not roots is passed,
     * the error will not be detected by this Constructor.
     * 
     * @param roots an int[][], which will be interpreted as a list of roots
     * @param s a String, which will be the "prefix" on all the variables.
     * @throws NotARootException if the int[][] passed does not consist of roots
     */
    public Unipotent( final int[][] roots, final String s) throws NotARootException {

	group = Group.getGroup(roots[0].length);                                      

	// create a list of Sunipotents 
	List<Sunipotent> list = new ArrayList<Sunipotent>();
	
	// create a Bidi map for associations
	BidiMap<Sunipotent, String> map = 
	    new DualHashBidiMap<Sunipotent, String>();
	
	// for each root on the list.
	for (int i = 0; i < roots.length; i++)
	{
	    /*  we make a Sunipotent.  The first step is to build the 
	     * variable associated to our root.
	     * 
	     * Begin with the String s, add a short string representation of the root.
	     */
	    String si = defaultString(s,roots[i]);
	    
	    
	    /* Now form a Sunipotent whose root is our root and whose 
	     * argument is the variable we just built, regarded as a very simple
	     * Polynomial.
	     */
	    Sunipotent x;
		x = Sunipotent.create(roots[i], Polynomial.create(si));
		
		// add the Sunipotent to the product
	    list.add(x);
	    // add the pair to the map.
	    map.put(x, si);
	    
	    
	}
	
	product = list;
	immobile = new ArrayList<Sunipotent>(list); 
	// all Sunipotents are immobile
	associations = map ; 
	// every Sunipotent owns the variable with which it is initialized.
    }
    
    /*Our preferred constructors throw NotARootExceptions.  It is necessary to have a 
     * simple, safe constructor which does not throw checked exceptions so that one can 
     * assure that variables are always initialized.
     * 
     */
    
    
    
    /**
     * No argument Constructor.  Initializes everything to null.
     */
     public Unipotent() {
	group = null;
	immobile = null;
	product = null;
    }
     /**
      * Constructor. Instantiates the identity element (empty product) 
      * of the Group of the specified rank. 
     * @param rank the int representing the semisimple rank of the grouip
      */
      public Unipotent(final int rank ) {
 	group = Group.getGroup(rank);
 	immobile = new ArrayList<Sunipotent>();
 	product = new ArrayList<Sunipotent>();
     }
     /**
      * Default Constructor
     * @param product2 terms of desired product
     * @param group2 desired group
     * @param immobile2 indicates which terms are "immobile" (for simplification algorithms.)
     * @param associations2 desired list of associations (for change of variable algorithms.)
     */
    public Unipotent(List<Sunipotent> product2, Group group2,
	    List<Sunipotent> immobile2,
	    BidiMap<Sunipotent, String> associations2) {
	product = new ArrayList<Sunipotent>(product2);
	group = group2;
	immobile = new ArrayList<Sunipotent>(immobile2);
	associations = new DualHashBidiMap<Sunipotent,String>(associations2);
    }
    /**
     * Creates a new association between a given Sunipotent and 
     * a given string 
     * 
     * 
     * @param suni Sunipotent  the sunipotent for the new association
     * @param s String   the string for the new association 
     */
    public void associate( Sunipotent suni , String s){
	if( suni != null && s != null)
	    associations.put(suni,s);
    }
	    
    /**
     *  Removes an association
     * @param suni the sunipotent to be disassociated
     */
    public void disassociate( Sunipotent suni){
	associations.remove(suni);
	
    }
    /**
     *  Removes an association
     * @param s the String to be disassociated
     */
    public void disassociate( String s){
	associations.removeValue(s);
	
    }
   
    /**
     * @return the list of (Sunipotent) terms of a Unipotent.
     */
    public List<Sunipotent> getTerms(){
	return product;
    }
    
    /**
     * Inserts the new Sunipotent at the given location.
     * 
     * @param location index in which to insert the new Sunipotent
     * @param newSuni  the Sunipotent to be inserted
     */
    public void add(int location, Sunipotent newSuni) {
	product.add(location, newSuni);
    }

    /**
     * Attempts to shuffle sunipotents around and combine terms with the same
     * root.
     * 
     * 
     */

    public void cleanUp() {
	/*TODO implement a "smart" cleanUp which begins by computing
	 * the "depth function" determined by the unipotent (or throwing a nonUnipotentException if unable to)
	 * and then decides which "fixes" to perform based on depth.  
	 */
	
	done = false;
	while (!done) {
	    done = true;
	    preFix();
	}

    }

    private void fix(int i, int j) {

	// We need to move the sunipotents at indices i,j together
	// we need logic to determine whether we push the one
	// on the right left or the one on the left right
	

	done = false;

	if (isMobile(i)) {

	    combineRight(i,j);
	
	} else {// this means j is mobile

	    
	    combineLeft(i,j);
	}
	
    }

    /**
     * Combines two Sunipotents with the same root at the position currently 
     * occupied by the one on the left. 
     * 
     * If s1 = x_a(p) and s2 = x_a(q), then s1*s2 = x_a(p+q).  In order to simplify 
     * unipotents, we seek out pairs of Sunipotents with the same root and try to 
     * combine them.  If the two are not currently adjacent, this process with 
     * involve commutation relations with any intervening terms.
     * 
     * E.G.  s1 s3 s4 s2 = s1 s2 (s2^{-1}, s3) s3 (s2^{-1}, s4) s4 
     * 
     * @param i integer, should satisfy -1 < i < j
     * @param j integer, should satisfy i < j < product.size
     * 
     */
    public void combineLeft(final int i, final int j) {
	// check that the combination is valid
	if(!(
		Arrays.equals(product.get(i).getRoot(), product.get(j).getRoot() )
		&& 
		(i < j))	
	)
		throw new RuntimeException();
	
	// formula: a b c = a c c^{-1} b c b^{-1} b = ac (c^{-1},b) b
	// whence: a b c ... e = ae (e^{-1}, b) b (e^{-1}, c) c ...

	
	Sunipotent sinv = Sunipotent.create(product.get(j).getRoot(), product.get(j).getArgument().times(-1));
	Sunipotent newTerm = 	Sunipotent.create( product.get(j).getRoot(), product.get(j).getArgument().plus(product.get(i).getArgument()));
	if( !(isMobile(i)&&isMobile(j)))
	    immobile.add(newTerm);
	immobile.remove(get(i));
	immobile.remove(get(j));
	if( stringOf(get(j))!= null)
	    associate(newTerm, stringOf(get(j)) );
	if( stringOf(get(i))!= null)
	    associate(newTerm, stringOf(get(i)) );
	product.remove(j);
	for( int k = j -1; k >i ; k--){
	    product.addAll(k, group.commutator(sinv, product.get(k)) );
	}
	product.remove(i);
	product.add(i,newTerm);
	
    }
    /**
    * Combines two Sunipotents with the same root at the position currently 
     * occupied by the one on the left. 
     * 
     * If s1 = x_a(p) and s2 = x_a(q), then s1*s2 = x_a(p+q).  In order to simplify 
     * unipotents, we seek out pairs of Sunipotents with the same root and try to 
     * combine them.  If the two are not currently adjacent, this process with 
     * involve commutation relations with any intervening terms.
     * 
     * E.G.  s1 s3 s4 s2 = (s1,s3) s3 (s1,s4) s4 s1 s2 
     * 
     * @param i integer, should satisfy -1 < i < j
     * @param j integer, should satisfy i < j < product.size
     */
    public void combineRight(final int i, final int j) {
	// check that the combination is valid
	if(!(
		Arrays.equals(product.get(i).getRoot(), product.get(j).getRoot() )
		&&
		i<j))
		throw new RuntimeException();
	
	
	// formula a b c = a b a^{-1} b^{-1} b a c = (a,b) b ac
	// whence: a b c ... e = (a,b) b (a,c) c ... ae.
	Sunipotent s = product.get(i);
	Sunipotent newTerm = 	Sunipotent.create( product.get(j).getRoot(), product.get(j).getArgument().plus(product.get(i).getArgument()));
	if( !(isMobile(i)&&isMobile(j)))
	    immobile.add(newTerm);
	immobile.remove(get(i));
	immobile.remove(get(j));
	if( stringOf(get(i))!= null)
	    associate(newTerm, stringOf(get(i)) );
	if( stringOf(get(j))!= null)
	    associate(newTerm, stringOf(get(j)) );
	product.remove(j);
	product.add(j, newTerm);
	for(int k = j-1; k > i ; k--){
	    product.addAll(k, group.commutator(s, product.get(k)));
	}
	product.remove(i);
    }
    /**
     * Returns the Sunipotent at the specified position in the product.
     * 
     * @param index  the index of the term to be retrieved
     * @return the term at the position specified in the list of Sunipotents
     */
    public Sunipotent get(int index) {
	return product.get(index);
    }
 
    /**
     * Get the last (rightmost) term in the product of sunipotents.
     * @return the last sunipotent
     */
    public Sunipotent getLast() {
	if(product.size()==0)
	    return null;
	return product.get(product.size()-1);
    }
    
    /**
     * Gets the polynomial argument of the ith term.
     * @param i integer, index of term 
     * @return the polynomial argument of this term, or null if the index is out of range.
      */
   public Polynomial getArg( int i  ){
	return (-1 < i && i < product.size() ) ? get(i).getArgument(): null ;
	
    }
    
     /**
     * Gets the number of terms in the product of Sunipotents.
     * 
     * @return the number of Sunipotents in this Unipotent
     */
    public int getNumberOfTerms() {
	return product.size();
    }

    /**
     * Returns the ambient root system in which this Unipotent lives.
     * 
     * @return the root system for which this Unipotent is an element of
     */
    public Group getGroup() {
	return this.group;
    }

    /**
     * Finds the first sunipotent in the product that has the specified root. If
     * such a sunipotent cannot be found in the product, -1 is returned.
     * 
     * @param root    the root to search for
     * @return the position of the specified root or -1 if not found
     */
    public int indexOf(int[] root) {
	for (int i = 0; i < product.size(); i++)
	    if (Arrays.equals(product.get(i).getRoot(), root))
		return i;
	return -1;
    }

    /**
     * Finds the last sunipotent in the product that has the specified root. If
     * such a sunipotent cannot be found in the product, -1 is returned.
     * 
     * @param root    the root to search for
     * @return the position of the specified root or -1 if not found
     */
    public int lastIndexOf(int[] root) {
	for (int i = product.size()-1; i>-1;  i--)
	    if (Arrays.equals(product.get(i).getRoot(), root))
		return i;
	return -1;
    }

    /**
     * Tries to find a sunipotent in the product that has a root that matches
     * any of the specified roots. If no sunipotent element in the product can
     * be found, -1 is returned.  Search sunipotents left to right, roots 
     * in listed order.
     * 
     * 
     * @param roots the list of roots to search for
     * @return the index of the first sunipotent from the left that matches r0,
     *         where r0 is the first root in the specified list which has a
     *         match, or -1 if none of the roots in the list has a match.
     */
    public int indexOf(int[][] roots) {
	for (int i = 0; i < product.size(); i++) 
	    for( int j = 0; j< roots.length; j++)
		if(Arrays.equals(get(i).getRoot(), roots[j]))
		    return i;
	return -1;
    }
 
    
    /**
     * If 
     * u = x_{a_1}(r_1) ... x_{a_N}(r_N) 
     * is a unipotent and m is an int[][], then u.indexOf(m) is 
     * the smallest integer i with the property that a_i is an 
     * element of m.
     * @param roots list of roots to check for
     * @return the index of the first term whose root is on the given list.
     */
    public int indexOf(List<int[]> roots) {
	for (int i = 0; i < product.size(); i++) 
	    for( int j = 0; j< roots.size(); j++)
		if(Arrays.equals(get(i).getRoot(), roots.get(j)))
		    return i;
	return -1;
    }

    /**
     * Tries to find a sunipotent in the product that has a root that matches
     * any of the specified roots, starting from the specified point. If no 
     * sunipotent element in the product can
     * be found, -1 is returned.  Search sunipotents left to right, roots 
     * in listed order.
     * 
     * 
     * @param roots the list of roots to search for
     * @param startPoint the place to start looking
     * @return the index of the first sunipotent from the left that matches r0,
     *         where r0 is the first root in the specified list which has a
     *         match, or -1 if none of the roots in the list has a match.
     */
public int indexOf(final int[][] roots, final int startPoint) {
	for (int i = startPoint; i < product.size(); i++) 
	    for( int j = 0; j< roots.length; j++)
		if(Arrays.equals(get(i).getRoot(), roots[j]))
		    return i;
	return -1;
    }
    
    /**
     * Tries to find a sunipotent in the product that has a root that matches
     * any of the specified roots. If no sunipotent element in the product can
     * be found, -1 is returned.  Search roots in listed order, sunipotents right
     * to left.
     * 
     * @param roots   the list of roots to search for
     * @return the index of the last sunipotent that matches any of the roots
     *         in the specified list or -1 if no such sunipotent element can be
     *         found
     */
    public int lastIndexOf(int[][] roots) {
	for( int i = product.size()-1; i>-1; i--)
	    for( int j = 0 ; j < roots.length; j++)
		if(Arrays.equals(get(i).getRoot(), roots[j]))
		    return i;
	    
	
	return -1;
    }

    private boolean isMobile(int i) {
	return !immobile.contains(product.get(i));
    }

    private void preFix() {

	int i = 0;
	while( i < product.size() - 1)
	{
	    int j = i + 1;
	    while( j < product.size()){	
		if (Arrays.equals(product.get(i).getRoot(), product.get(j)
			.getRoot())){
		    
		    fix(i, j);
		    /*
		     *fix will leave terms 0 through i-1 alone.  However, it may:
		     * - push the ith term right so that the i+1st term or a new term
		     *created by conjugation becomes the ith term.
		     * - create new terms between i and j, which have not yet been compared
		     * to the terms in positions 0 through i. 
		     * 
		     */
		    j=Math.max(i, 1); // this is the first term which may be new,
		    i = 0; // we put i back to 1, so that all new terms will be checked against all old terms.
		    //FIXME (?) this is modestly inefficient, since it re-checks 2 to (i-1) unnecessarily.
		    
		}
		else
		    j++;
	    }
	    i++;
	}
    }

    /**
     * Shifts sunipotent at the given index to the left all the way to the end
     * of the list.
     * 
     * @param index  the index of the sunipotent to be pushed
     * @return the final position of the sunipotent
     */
    public int pushFarLeft(int index) {
	while (index != 0) {
	    index = pushLeft(index);
	}
	return index;
    }

     /**
     * Pushes the given sunipotent all the way to the left, removes it, then
     * calls cleanUp.
     * 
     * @param index   the sunipotent to be moved.
     */
    public void pushFarLeftAndRemove(int index) {
	remove(pushFarLeft(index));
	cleanUp();
    }

    /**
     * Shifts sunipotent at the given index to the right all the way to the end
     * of the list.
     * 
     * @param index   the index of the sunipotent to be pushed
     * @return the final position of the sunipotent
     */
    public int pushFarRight(int index) {
	while (index != product.size() - 1) {
	    index = pushRight(index);
	}
	return index;
	/*
	 * FIXME Suppose your term is pushed right until it hits another term 
	 * with the same root.  Then this method may produce strange and unwanted
	 * behavior.
	 */
    }

    /**
     * Pushes the given sunipotent all the way to the right, removes it, then
     * calls cleanUp.
     * 
     * @param index   the sunipotent to be moved.
     */
    public void pushFarRightAndRemove(int index) {
	remove(pushFarRight(index));
	cleanUp();
	/*
	 * FIXME if the element you push right has the same root as another element
	 * which is to its right, this method will produce strange and unwanted behavior.
	 * 
	 */
    }

    /**
     * Shifts Sunipotent at given index to the left by one. If this commutation
     * requires the addition of new terms, they are properly inserted.
     * 
     * 
     * @param index the element to be pushed left
     * @return the location of the element that was pushed left, except
     * in the case of cancellation.  in case of cancellation, the 
     * value returned is index-1, while the Sunipotent pushed is gone.
     * (Note that if the last two terms cancel, this will NOT be the 
     * index of an element of the unipotent).
     */

    public int pushLeft(int index) {
	index--;
	if (index >= product.size() - 1 || index < 0)
	    throw new IndexOutOfBoundsException();
	int[] a = product.get(index).getRoot();
	int[] b = product.get(index + 1).getRoot();
	if (Arrays.equals(a, b)) {
	    Polynomial newPoly = product.get(index).getArgument().plus(
		    product.get(index + 1).getArgument());
	    if (newPoly != Polynomial.create(0)) {
		/* replace Suni at index with a new Suni.
		 * (simply modifying the polynomial of this Sunipotent will break old code
		 *  which does something while product contains existing one... )
		 */  
		// manage associations 
		Sunipotent newSuni = Sunipotent.create(product.get(index)
			.getRoot(), newPoly);
		associate( newSuni, associations.get( product.get(index)));
		associate(newSuni, associations.get(product.get(index+1)));

		if(!( isMobile(index) && isMobile(index+1)))
		    immobile.add(newSuni);

		product.set(index, newSuni);
		// suni at index absorbs the one at index+1, so remove the one at index+1
		remove(index + 1);
		if(!( isMobile(index) && isMobile(index+1)))
		    immobile.add(newSuni);
	    }
	    else // terms cancel
	    {
		remove(index+1);
		remove(index);
	    }
	    return index;
	}
	List<Sunipotent> ab = group.commutator(product.get(index), product
		.get(index + 1));
	product.addAll(index, ab);

	index = index + ab.size();
	Collections.swap(product, index, index + 1);
	return index;
    }

    /**
     * Shifts Sunipotent at given index to the right by one. If this commutation
     * requires the addition of new terms, they are properly inserted.
     * If the next sunipotent right has the same root, then the two 
     * are combined.
     * 
     * @param index the index of the term to be pushed to the right by one
     * @return the location of the element that was shifted right, except 
     * in the case of cancellation. In that case, it returns index.
     * (Note that if the last two terms cancel, this will NOT be the 
     * index of an element of the unipotent).
     */

    public int pushRight(int index) {
	
	if (index >= product.size() - 1 || index < 0){
	    System.out.println("pushRight handed argument "+ index + 
		    " max allowable is "+Integer.toString(product.size()-2)+"\n"
		    +this.toStringWithIndices());
	    
	    throw new IndexOutOfBoundsException();
	}
	int[] a = product.get(index).getRoot();
	int[] b = product.get(index + 1).getRoot();
	if (Arrays.equals(a, b)) {
	    Polynomial newPoly = product.get(index).getArgument().plus(
		    product.get(index + 1).getArgument());
	    if (newPoly != Polynomial.create(0)) {
		Sunipotent newSuni = Sunipotent.create(product.get(index)
			.getRoot(), newPoly);
		associate(newSuni, associations.get( product.get(index)));
		associate(newSuni, associations.get(product.get(index+1)));

		if(!( isMobile(index) && isMobile(index+1)))
		    immobile.add(newSuni);

		
		product.set(index, newSuni);
		remove(index + 1);
	    }
	    else
	    {
		remove( index+1);
		remove(index);
		
	    }
	    return index;
	}

	List<Sunipotent> ab = group.commutator(product.get(index), product
		.get(index + 1));
	product.addAll(index, ab);

	index = index + ab.size();

	Collections.swap(product, index, index + 1);
	return index + 1;

    }
    
    /**
     * @param from index of sunipotent to move
     * @param to location it should be moved to.  more precisely, this should be the index of the first existing 
     * sunipotent which should be after the one we're moving after we move it.  if desired location is last, then 
     * will be product.size()+1.
     */
    public void move(int from , int to ){
	if(to > product.size()-1)
	    pushFarRight(from);
	else {
	    Sunipotent movedOne = product.get(from);
	    Sunipotent currentlyAtTo = product.get(to);

	    boolean done = false;
	    while (!done) {
		done = true;
		if (product.indexOf(movedOne) > product.indexOf(currentlyAtTo)) {
		    this.pushLeft(product.indexOf(movedOne));
		    done = false;
		}
		if (product.indexOf(movedOne) < product.indexOf(currentlyAtTo)-1) {
		    done = false;
		    this.pushRight(product.indexOf(movedOne));
		}
	    }// end while not done
	}// end if to > product.size() else
	
    }

    /**
     * Removes the i-th term in this Unipotent.
     * 
     * @param i the index of the term to be removed.
     */
    public void remove(int i) {
	if( associations.containsKey(product.get(i)))
	    associations.remove(product.get(i));
	if(!isMobile(i))
	    immobile.remove(get(i));
	product.remove(i);
    }
    /**
     * Remove a Sunipotent term.
     * @param s the Sunipotent to be removed
     */
    public void remove(final Sunipotent s) {
	if( associations.containsKey(s))
	    associations.remove(s);
	    immobile.remove(s);
	product.remove(s);
    }
    

     /**
      * Simplifies the unipotent, by making substitutions based on the associations between 
      * Sunipotents and variables.  Records the effect of these substitutions on a given 
      * polynomial.
      * 
      * @param p a polynomial
      * @return the polynomial p after a number of substitutions have been made, based on 
      * the associations stored in this unipotent.
     * @throws BadSubstitutionException if any substitution is made for a variable which appears to a negative exponent.
      */
    public Polynomial chOfVars(Polynomial p) throws BadSubstitutionException {
	/*This is probably a good place to remind the reader that an object of class Unipotent stores 
	 * a list of associations between Strings (thought of as variables) and Sunipotents.  
	 * This method is the sort of thing for which these associations are intended.  
	 * 
	 * Not every Sunipotent will be associated to a variable, and not every variable will be 
	 * associated to a Sunipotent.  In order for things to work properly, no Sunipotent may be 
	 * associated to more than one variable and no variable may be associated to more than 
	 * one Sunipotent.  
	 * 
	 * In this method, if a Sunipotent is associated to a variable s, then the method tries to make
	 * an appropriate substitution so that, after substitution the argument of the Sunipotent is s.
	 * 
	 */
	for (int i = 0; i < getNumberOfTerms(); i++) {
	    
	    /* get the String associated to Sunipotent i, 
	     * (If Sunipotent i has no String, then stringOf() returns "null."
	     */
	    String s1 = stringOf(get(i));
	    
	    
	    if (s1 != null) {// i.e., if our Sunipotent is indeed associated to a variable...
		
		/* there are two cases that can be handled. Write arg = current argument of our Sunipotent.
		 * 1. arg = s1 + q, where q is independent of s1.  In this case, the substitution 
		 * 	s1 -> s1 - q is indicated.
		 * 2. arg = -s1+q.  In this case, the substitution s1 -> (-s1+q) is indicated.  
		 * 
		 */
		// rewrite condition 1. above as "q:= arg - s1 is independent of s1."
		if( get(i).getArgument().minus(Polynomial.create(s1)).isIndependentOf(s1)){ 
		    
		    // p1:= s1-q = 2 s1 - arg.
		    Polynomial p1 = Polynomial.create(s1).times(2).minus(
			get(i).getArgument());
		    
		    // s1 -> p1
		    p = p.replace(s1, p1); // in the Polynomial p which was passed to this method by the caller,
		    this.replace(s1, p1);// and in this Unipotent
		}
		// rewrite condition 2. above as q:= arg + s1 is independent of s1."  
		if( get(i).getArgument().plus(Polynomial.create(s1)).isIndependentOf(s1)){ 
		    
		    // p1:= -s1+q = arg.
		    Polynomial p1 = get(i).getArgument();
		    
		    // s1 -> p1
		    p = p.replace(s1, p1); // in the Polynomial p which was passed to this method by the caller,
		    this.replace(s1, p1);// and in this Unipotent
		    
		}

	    
	    }// end if s1 not null
		

	}// end for each term...
	return p;
    }// end ChOfVars
    
    /**
     * Replaces a given String variable by a given Polynomial throughout.  
     * Immobility is preserved. Any term which is associated to a variable 
     * which is not s1 will remain associated to that variable.  A term which 
     * is associated to s1 will no longer have an associated variable, unless
     * p1 is itself a variable, in which case it will inherit s1's association.
     * @param s1 varible, for which to substitute
     * @param p1 to plug in for s1
     * @throws BadSubstitutionException if s1 appears to a negative exponent and p1 is not a signed monomial
     */
    public void replace(String s1, Polynomial p1) throws BadSubstitutionException {
	ArrayList<Sunipotent> newProduct = new ArrayList<Sunipotent>();
	ArrayList<Sunipotent> newImmobile = new ArrayList<Sunipotent>();
	DualHashBidiMap<Sunipotent, String> newAssociations = new DualHashBidiMap<Sunipotent, String>();
	for( int i = 0 ; i < product.size(); i++){
		Polynomial arg = get(i).getArgument();
		Polynomial newArg = arg.replace(s1, p1);
		String associate = stringOf(get(i));
		Sunipotent replacement = Sunipotent.create(get(i).getRoot(), newArg);
		newProduct.add(replacement);
		if(!isMobile(i)){
		    
		    newImmobile.add(replacement);
		}
		if(associate != null && !associate.equals(s1)){
		    newAssociations.put(replacement, associate);
		}
		if( associate == s1 && p1.isAVariable()){
		    newAssociations.put(replacement, p1.getVar());
		}
	}
		product.removeAll(product);
		product.addAll(newProduct);
		associations = newAssociations;
		immobile.removeAll(immobile);
		immobile.addAll(newImmobile);
		    
		
	    
	
	
	
    }
    /**
     * Replaces a given String variable by a given Polynomial throughout.  
     * Immobility is preserved. Any term which is associated to a variable 
     * which is not s1 will remain associated to that variable.  A term which 
     * is associated to s1 will no longer have an associated variable, unless
     * p1 is itself a variable, in which case it will inherit s1's association.
     * @param s1 varible, for which to substitute
     * @param p1 to plug in for s1
     * @throws BadSubstitutionException if s1 appears to a negative exponent and p1 is not a signed monomial
     */
    public void replaceINeedABetterName(String s1, Polynomial p1) throws BadSubstitutionException {
	ArrayList<Sunipotent> newProduct = new ArrayList<Sunipotent>();
	ArrayList<Sunipotent> newImmobile = new ArrayList<Sunipotent>();
	DualHashBidiMap<Sunipotent, String> newAssociations = new DualHashBidiMap<Sunipotent, String>();
	for( int i = 0 ; i < product.size(); i++){
		Polynomial arg = get(i).getArgument();
		Polynomial newArg = arg.replace(s1, p1);
		String associate = stringOf(get(i));
		Sunipotent replacement = Sunipotent.create(get(i).getRoot(), newArg);
		newProduct.add(replacement);
		if(!isMobile(i)){
		    
		    newImmobile.add(replacement);
		}
		if(associate != null ){
		    newAssociations.put(replacement, associate);
		}
	}
		product.removeAll(product);
		product.addAll(newProduct);
		associations = newAssociations;
		immobile.removeAll(immobile);
		immobile.addAll(newImmobile);
		    
		
	    
	
	
	
    }
    /**
     * This method, together with the machinery of "associations" facilitates certain change of 
     * variables algorithms.  Suppose the Sunipotent x_a(r_a) is associated to the default variable
     * r_a.  Then, in most situations rather than allow some algebraic manipulation to complicate
     * the argument of x_a, we shall simply make a substitution for r_a to insure that the argument
     * of x_a is always r_a.  For purpose of such manipulations, it makes sense
     * to simply skip the term x_a(r_a).  
     * 
     * @param s1 variable for which a substitution is made.
     * @param p1 plugged in
     * @param j term to skip
     * @throws BadSubstitutionException if s1 appears with a negative exponent.
     */
    public void replaceWithAnException(String s1, Polynomial p1, int j) throws BadSubstitutionException {
	ArrayList<Sunipotent> newProduct = new ArrayList<Sunipotent>();
	ArrayList<Sunipotent> newImmobile = new ArrayList<Sunipotent>();
	DualHashBidiMap<Sunipotent, String> newAssociations = new DualHashBidiMap<Sunipotent, String>();
	for( int i = 0 ; i < product.size(); i++){
	    
		Polynomial arg = get(i).getArgument();
		Polynomial newArg;
		if(i != j){
		 newArg = arg.replace(s1, p1);
		}
		else 
		    newArg  = arg;
		String associate = stringOf(get(i));
		Sunipotent replacement = Sunipotent.create(get(i).getRoot(), newArg);
		newProduct.add(replacement);
		if(!isMobile(i)){
		    
		    newImmobile.add(replacement);
		}
		if(associate != null){
		    newAssociations.put(replacement, associate);
		}
	    
	}
		product.removeAll(product);
		product.addAll(newProduct);
		associations = newAssociations;
		immobile.removeAll(immobile);
		immobile.addAll(newImmobile);
		    
		
	    
	
	
	
    }
    /**
     * Returns a string representation of this Unipotent.
     * 
     * @see java.lang.Object#toString()
     */

    public String toString() {
	if (product.size() != 0) {
	    int currentLineLength = 0;
	    StringBuffer sb = new StringBuffer();
	    for (int i = 0 ; i < product.size(); i++) {
		if( currentLineLength + product.get(i).toString().length() > edu.siu.math.egut.io.Constants.SCREEN_WIDTH)
		{
		    sb.append("\n");
		    currentLineLength = 0;
		}// end if currentlinelength + .. > .. 
		sb.append(product.get(i).toString()+" " );
		currentLineLength += 1 + product.get(i).toString().length();
	    }
	    return sb.toString();
	} else {
	    return "(empty unipotent)";

	}
    }
    public String toString(boolean abbreviated) {
	if (product.size() != 0) {
	    int currentLineLength = 0;
	    StringBuffer sb = new StringBuffer();
	    for (int i = 0 ; i < product.size(); i++) {
		String nextTerm = product.get(i).toString(abbreviated);
		if( currentLineLength + nextTerm.length() > edu.siu.math.egut.io.Constants.SCREEN_WIDTH)
		{
		    sb.append("\n");
		    currentLineLength = 0;
		}// end if currentlinelength + .. > .. 
		sb.append(nextTerm+" " );
		currentLineLength += 1 + nextTerm.length();
	    }
	    return sb.toString();
	} else {
	    return "(empty unipotent)";

	}
    }
       
    /**
     * Returns a string representation of this Unipotent in a tabular format with the index of each Sunipotent indicated.f
     * 
     * TODO look around for something to facilitate output that looks at how long the lines are and puts breaks when it 
     * needs to.
     * @return String representation 
     * 
     * @see java.lang.Object#toString()
     */
    public String toStringWithIndices() {
	if (product.size() != 0) {
	    int currentLineLength = 0;
	    StringBuffer sb = new StringBuffer();
	    for (int i = 0 ; i < product.size(); i++) {
		if( currentLineLength + product.get(i).toString().length() > edu.siu.math.egut.io.Constants.SCREEN_WIDTH)
		{
		    sb.append("\n");
		    currentLineLength = 0;
		}// end if currentlinelength + .. > .. 
		sb.append(i + " "+product.get(i).toString()+"  " );
		currentLineLength += 3 + product.get(i).toString().length()+(int) Math.floor(Math.log10(Math.max(1, i)));
	    }
	    return sb.toString();
	} else {
	    return "(empty unipotent)";

	}
    }
    public String toStringWithIndices(boolean abbreviated) {
	if (product.size() != 0) {
	    int currentLineLength = 0;
	    StringBuffer sb = new StringBuffer();
	    for (int i = 0 ; i < product.size(); i++) {
		if( currentLineLength + product.get(i).toString(abbreviated).length() 
			> edu.siu.math.egut.io.Constants.SCREEN_WIDTH)
		{
		    sb.append("\n");
		    currentLineLength = 0;
		}// end if currentlinelength + .. > .. 
		sb.append(i + " "+product.get(i).toString(abbreviated)+"  " );
		currentLineLength += 3 + product.get(i).toString(abbreviated).length()+(int) Math.floor(Math.log10(Math.max(1, i)));
	    }
	    return sb.toString();
	} else {
	    return "(empty unipotent)";

	}
    }
    
    
    /**
     * Gets the string associated to the given Sunipotent (which may be null)
     * 
     * @param suni Sunipotent
     * @return associated string if there is one, or null.
     */
    public String stringOf( Sunipotent suni){
	return associations.get( suni );
    }
    
    /**
     * Gets the sunipotent associated to the given strong (which may be null)
     * @param s String
     * @return assocatated Sunipotent, or null if there is none.
     */
    public Sunipotent suniOf( String s){
	
	return associations.getKey( s);
    }
    /**
     * @return true if any of the arguments of the terms has a negative exponent
     */
    public boolean hasNegativeExponents() {
	for(final Sunipotent s: this.getTerms())
	    if(s.hasNegativeExponents())
		return true;
	return false;
    }

    /**
     * Checks for Sunipotents with argument zero and removes any that it finds.
     */
    public void clearZeros() {
	int i = 0;
	while( i < product.size()){
	    if(product.get(i).getArgument() == Polynomial.create(0)){
		associations.removeValue(product.get(i));
		immobile.remove(product.get(i));
		product.remove(i);
	    }
	    else 
		i++;
	}
	
    }
    /**
     * Gets the index of the given Sunipotent.  If u is a unipotent, then it is a product of
     * Sunipotents s_1 s_2 .... s_N.
     * 
     * If s is a Sunipotent, then u.getIndex(s) is equal to i if s == s_i, and -1 if s does not
     * appear in u.
     * @param sunipotent whose location in our Unipotent is desired
     * @return i if the given Sunipotent appears at position i in our unipotent, and -1 if it does not appear.
     */
    public int getIndex(final Sunipotent sunipotent) {
	return product.indexOf(sunipotent);
    }
    /**
     * Serialization and deserialization can sometimes allow Sunipotents to sneak 
     * into existence without being entered into the Sunipotent store.  
     * This corrects that problem.
     * @return a Unipotent with the same underlying data, in which every 
     * Sunipotent has been run through Sunipotent.update()
     */
    public Unipotent update() {
	for( int i = 0 ; i < product.size(); i++ )
	{

	    final Sunipotent s1 = Sunipotent.update(get(i));
	    if( immobile.contains(get(i))){
		immobile.remove(get(i));
		immobile.add(s1);
		
	    }
	    if(stringOf( get(i))!=null){
		associate( s1, stringOf(get(i)));
		disassociate(get(i));
	    }
	    product.remove(i);
	    product.add(i,s1);
	    
	    
	}
	return this;
	
    }
    
    /*
     * The remaining methods are only used in EGUT program SectionIntegral which is currently at a very early stage of 
     * development.  I am not convinced that they will make it into the final version.
     */
    
    
    /**
     * Drops one or more terms from the unipotent if they have a specified root.
     * @param r an int[] representing the root
     * @param p a polynomial to be manipulated in conjunction with the unipotent.
     * @param scanner a Scanner for user input
     * @return the polynomial obtained by making appropriate substitutions in p.
     * @throws BadSubstitutionException if a substitution is made for a variable which appears to a negative power
     * @deprecated This method appears to be left over from an older SectionIntegral Calculator.  This should probably be a method for class SectionIntegral or SectionIntegralCalculator, not Unipotent.
     */
    public Polynomial dropRoot(final int[] r, final Polynomial p, final Scanner scanner) throws BadSubstitutionException {
	if(this.indexOf(r)== -1){
	    System.out.println("Root not found in unipotent.");
	    return p;
	}
	if((this.indexOf(r) == this.lastIndexOf(r))&& get(indexOf(r)).getArgument()==Polynomial.create(stringOf(get(indexOf(r))))){
	    return killVariable( stringOf(get(indexOf(r))),p);
	}
	Polynomial q =p;
	System.out.println("Multiple terms with this root found.");
	for(Sunipotent s:product){
	    if(Arrays.equals(s.getRoot(), r)){
		System.out.println(s+"\n[K]ill term\t[S]kip term"+(stringOf(s)==null?"":("[C]hange of vars: "+stringOf(s)+"->0")));
		char response = edu.siu.math.egut.io.Algorithms.getMenuAnswer(DROP_ROOT_MENU_OPTIONS,	 scanner);
		if( response == 'K'||response == 'k'){
		    remove(s);
		    
		}
		else if(response =='C'||response =='c'){
		    q = killVariable(stringOf(s),q);
		}
		    
	    }
	}
	return q;
    }
    
    
    /**
     * Sets a given variable equal to zero in both the Unipotent object which 
     * calls it, and a given Polynomial.
     * @param s String, a varaible
     * @param p a Polynomial
     * @return p, after s has been replaced by zero.
     * @throws BadSubstitutionException 
     * @deprecated this should probably be a method in Piece, not Unipotent
     */
    private Polynomial killVariable(String s, Polynomial p) throws BadSubstitutionException {
	replace(s,Polynomial.create(0));
	clearZeros();
	return p.replace(s, Polynomial.create(0));
    }
    /**
     * Modifies the unipotent according to the adjoint action of a specified group element.  
     * 
     * 
     * @param string should be readable as a group element
     * @throws NoSuchElementException if the given string is not readable as a group element
     */
    public void actBy(final String string) throws NoSuchElementException {
	/*For now we support two types of group elements:  simple unipotents and Weyl elements. 
	 */
	// if the String is readable as a simple unipotent 
	Sunipotent s = Sunipotent.readWithChecks(string, group);
	if( s != null){
	    actBy(s);
	}
	else{ 
	    // try to read the string as a Weyl element and act by that element if successful.
	    if(Algorithms.representsWeylWord(edu.siu.math.egut.io.Algorithms.removeWhiteSpaceCommasAndBrackets(string), group.getRank())){
		actByWord(edu.siu.math.egut.io.Algorithms.removeWhiteSpaceCommasAndBrackets(string));
	    }
	    else 
		throw new NoSuchElementException();
	}
	
	
    }
    
    /**
     * Conjugates the unipotent by a word in the standard 
     * representatives for the simple reflections in the 
     * Weyl group.
     * @param wordString a string, interpreted as a word in the
     * simple reflections, with each digit being an individual 
     * reflection.  An error will result if any character is 
     * not a digit between 1 and the rank of the ambient group.
     */
	public void actByWord(final String wordString) {
	
	for(int i = 0 ; i < product.size(); i++){
	    Sunipotent newSuni = get(i).imageUnder(wordString);
	    if(isMobile(i)){
		immobile.remove(get(i));
		immobile.add(newSuni);
	    }
	    if( stringOf(get(i))!=null){
		associate(newSuni, stringOf(get(i)));
	    }
	    product.remove(i);
	    product.add(i,newSuni);
		
	}
	    
	
    }

    
    
    
    
    /**
     * Acts by the (inner automorphism attached to) the given Sunipotent s.
     * If u is a unipotent and s is a Sunipotent then u.actBy(s) is the Unipotent
     * representing s u s^{-1} (after some simplification).
     * @param s to act.
     */
    public void actBy(final Sunipotent s) {
	
	leftMultiply(s);
	this.rightMultiply(Sunipotent.create(s.getRoot(), s.getArgument().times(-1)));
	cleanUp();
	this.clearZeros();
	cleanUp();
	
	
    }
     /**
      * Reads String representation of Unipotent and returns the desired object.
      * This method is deliberately non-fault-tolerant:  it is used mainly 
      * to read plaintext setup files.  If the setup file is not formatted 
      * correctly, the desired behavior is generally to terminate, so that the 
      * user can fix the setup file and try again.
     * @param s representing Unipotent
     * @return represented by s
     * @throws UnipotentReadException if input can not be read
     */
    public static Unipotent read(String[] s) throws UnipotentReadException {
	 if(s.length==0 )
	     return null;
	 if(! edu.siu.math.egut.io.Algorithms.SUNIPOTENT_OF_UNSPECIFIED_RANK.matcher(s[0]).matches())
	     throw new UnipotentReadException();
	 Sunipotent s1= Sunipotent.read(s[0]);
	 if( s1== null)
	     throw new UnipotentReadException();
	 Group group = Group.getGroup(s1.getRoot().length);
	 ArrayList<Sunipotent> prod = new ArrayList<Sunipotent>();
	 prod.add(s1);
	 for( int i = 1; i < s.length; i++)
	     if(edu.siu.math.egut.io.Algorithms.suniString(group).matcher(s[i]).matches()){
		 Sunipotent si = Sunipotent.readWithChecks(s[i], group);
		 if(si== null)
		     throw new UnipotentReadException();
		 prod.add(si);
	     }
	 
	 return new Unipotent(group, prod);
     
     }
    /**
     * @param string representing Unipotent in roots, prefix format
     * @return pair consisting of desired Unipotent and prefix
     * @throws NotARootException if "roots" portion of String contains a non-root
     * @throws UnipotentReadException if String is not of a recognizable InputStyle
     * @deprecated The idea of working with "prefixes" beyond the input format
     * itself has been essentially abandoned. 
     */
    public static UnipotentPrefixPair read(String string) throws NotARootException, UnipotentReadException {
	if(inputStyle(string) != InputStyle.NONSENSE )
	    return read( string, inputStyle( string ));
	throw new UnipotentReadException();
    
    }
    private static UnipotentPrefixPair read(String string, InputStyle inputStyle) throws NotARootException {
	switch (inputStyle)
	{
	case ROOTS_PLUS_STRING:
	    return new UnipotentPrefixPair(new Unipotent(parseRoots(string), parseString(string)), string);
	
	}
	return null;
	
    }
    private static String parseString(String string) {
	return string.substring(string.indexOf("prefix")+6).trim();
    }
    private static int[][] parseRoots(String string) {
	return edu.siu.math.egut.io.Algorithms.readLiEMatrix(string);
    }
    private static InputStyle inputStyle(String string) {
	if(ROOTS_PLUS_STRING_PATTERN.matcher(string).matches())
	    return InputStyle.ROOTS_PLUS_STRING;
	return InputStyle.NONSENSE;
    }
    /**
     * 
     * @param sty TEX or SCREEN (anything else is defaulted to SCREEN)
     * @return a string representation of this Unipotent in a specified OutputStyle.
     */
    public String toString(OutputStyle sty) {
	switch ( sty )
	{
	case TEX:
	StringBuilder sb = new StringBuilder("\\begin{array}{l}");
	int width =0;
	for(Sunipotent s: this.product){
	    if( width > 0 && width+s.toString(OutputStyle.SCREEN).length() > PAGE_WIDTH ){
		sb.append("\\\\\n");
		width = 0;
	    }
	    sb.append(s.toString(OutputStyle.TEX));
	    width = width+s.toString(OutputStyle.SCREEN).length();
	    }
	sb.append("\\end{array}");
	return sb.toString();
	
	}
	return this.toString();
    }
    public String toString(OutputStyle sty, boolean abbreviated) {
	switch ( sty )
	{
	case TEX:
	StringBuilder sb = new StringBuilder("\\begin{array}{l}");
	int width =0;
	for(Sunipotent s: this.product){
	    if( width > 0 && width+s.toString(OutputStyle.SCREEN, abbreviated).length() > PAGE_WIDTH ){
		sb.append("\\\\\n");
		width = 0;
	    }
	    sb.append(s.toString(OutputStyle.TEX, abbreviated));
	    width = width+s.toString(OutputStyle.SCREEN, abbreviated).length();
	    }
	sb.append("\\end{array}");
	return sb.toString();
	
	}
	return this.toString();
    }

    /**
     * @param x variable
     * @return true if the argument of each term in the product is independent of x.
     */
    public boolean isIndependentOf(String x) {
	for( Sunipotent s: this.product){
	    if(s.getArgument().dependsOn(x))
		return false;
	}
	return true;
    }
    /**
     * Replaces one Sunipotent with another throughout the Unipotent.
     * @param s existing Sunipotent
     * @param s1 replacement
     */
    public void replace(final Sunipotent s, final Sunipotent s1) {
	for( int i = 0 ; i < product.size(); i++)
	    if(product.get(i) == s){
		product.add(i,s1);
		product.remove(i+1);
	    }
	
    }
    /**
     * Removes the term at a specifed index and replaces it with a given new term.
     * @param i the index.
     * @param s1 the new term.
     */
    public void replace(int i, Sunipotent s1) {
	product.add(i,s1);
	product.remove(i+1);
	
    }
    /**
     * Sends a String representation of all associations to System.out.
     */
    public void listAssociations() {
	if(associations.isEmpty())
	    System.out.println("no associations.");
	
	ArrayList<int[]> assocRoots = new ArrayList<int[]>();
	for(Sunipotent s: associations.keySet()){
	    System.out.println(s.toString() +"<--->" + stringOf(s));
	    assocRoots.add(s.getRoot());
	}
	System.out.println(associations.size()+ " associations");
	System.out.println(edu.siu.math.egut.io.Algorithms.writeLieMatrix(assocRoots));
	
	
    }
    public static Unipotent copyOf(Unipotent u) {
	return new Unipotent(u.product, u.group, u.immobile, u.associations);
    }
    
    public boolean equals(Unipotent u){
	if(u.getNumberOfTerms()!= this.getNumberOfTerms())
	    return false;
	for(int i = 0; i < u.getNumberOfTerms(); i++)
	    if(!get(i).equals(u.get(i)) )
		return false;
	return true;
	
    }
    /**
     * Acts by (the inner automorphism attached to) the standard representative
     * for a Weyl word.
     * 
     * TODO figure out and explain what happens if the tuple given does not actually
     * represent a word in the relevant Weyl group.
     * 
     * @param word should represent a Word in the relevant Weyl group.
     */
    public void actBy(int[] word) {
	for( int i = word.length - 1 ; i > - 1; i--){
	    actBy(word[i]);
	}
	
    }
    public void addRight(ArrayList<Sunipotent> newSunipotents) {
	for(Sunipotent s: newSunipotents){
	    product.add(s);
	    if(s.getArgument().isAVariable() && suniOf(s.getArgument().getVar())== null)
		associate(s,s.getArgument().getVar());
	    immobile.add(s);
	}
	
    }
    public void replace(String s1, String p1) {
	ArrayList<Sunipotent> newProduct = new ArrayList<Sunipotent>();
	ArrayList<Sunipotent> newImmobile = new ArrayList<Sunipotent>();
	DualHashBidiMap<Sunipotent, String> newAssociations = new DualHashBidiMap<Sunipotent, String>();
	for( int i = 0 ; i < product.size(); i++){
		Polynomial arg = get(i).getArgument();
		Polynomial newArg = arg.replace(s1, p1);
		String associate = stringOf(get(i));
		Sunipotent replacement = Sunipotent.create(get(i).getRoot(), newArg);
		newProduct.add(replacement);
		if(!isMobile(i)){
		    
		    newImmobile.add(replacement);
		}
		if(associate != null && associate != s1){
		    newAssociations.put(replacement, associate);
		}
		if( associate == s1 )
		    newAssociations.put(replacement, p1);
	}
		product.removeAll(product);
		product.addAll(newProduct);
		associations = newAssociations;
		immobile.removeAll(immobile);
		immobile.addAll(newImmobile);
		    
		
	    
	
	
	
	
	
    }
    public void equalsVerbose(Unipotent u) {
	boolean equal = true;
	if(u.getNumberOfTerms()!= this.getNumberOfTerms()){
	    equal = false;
	    System.out.println(u.getNumberOfTerms() + "=/=" + this.getNumberOfTerms());
	}
	for(int i = 0; i < Math.max(u.getNumberOfTerms(),this.getNumberOfTerms()); i++){
	    if(i>=u.getNumberOfTerms()){
		System.out.println("Discrepancy at position "+ i);
		equal = false;
		System.out.println(get(i).toString()+"=/= null");
	    }else if (i>=this.getNumberOfTerms()){
		System.out.println("Discrepancy at position "+ i);
		equal = false;
		System.out.println("null =/="+u.get(i).toString());
	    }else  if(! get(i).equals(u.get(i))){
		System.out.println("Discrepancy at position "+ i);
		equal = false;
	    
	    if(getArg(i) != u.getArg(i) ){
		equal = false;
		System.out.println(getArg(i).toString() + "=/=" +u.getArg(i));
	    }
	    if(!Arrays.equals(get(i).getRoot(),u.get(i).getRoot())){
		equal = false;
		System.out.println(edu.siu.math.egut.io.Algorithms.tupleToString(get(i).getRoot())
			+"=/="+ edu.siu.math.egut.io.Algorithms.tupleToString(get(i).getRoot()));
	    }
	    }
	}
	if( equal)
	    System.out.println("Equal.");
	
    }
    public void replaceAndShiftAssociations(String s1, Polynomial p1) throws BadSubstitutionException {
//	System.out.println("Unipotent.replaceAndShiftAssociations() entered.");
	if( !p1.isASignedVariable())
	    throw new BadSubstitutionException("attempt to shift association to something other than a signed variable.");
	ArrayList<Sunipotent> newProduct = new ArrayList<Sunipotent>();
	ArrayList<Sunipotent> newImmobile = new ArrayList<Sunipotent>();
	DualHashBidiMap<Sunipotent, String> newAssociations = new DualHashBidiMap<Sunipotent, String>();
	for( int i = 0 ; i < product.size(); i++){
		Polynomial arg = get(i).getArgument();
		Polynomial newArg = arg.replace(s1, p1);
		Sunipotent replacement = Sunipotent.create(get(i).getRoot(), newArg);
		newProduct.add(replacement);

		if(!isMobile(i)){
		    
		    newImmobile.add(replacement);
		}

		
		
		String associate = stringOf(get(i));
//		System.out.println("Associate defined as "+get(i).toString()+"<-->"+ associate+"equals " + s1 +"? " + 
//			((associate.trim().equals(s1.trim()))?"yes":"no")+".");
		if(associate != null && !associate.trim().equals(s1.trim())){
		    newAssociations.put(replacement, associate);
		    
		}
		if( associate != null && associate.trim().equals(s1.trim()) ){
		    newAssociations.put(replacement, p1.getVar());
		}
	}
		product.removeAll(product);
		product.addAll(newProduct);
//		System.out.println("before reassigning assocations");listAssociations();//FIXME remove
		associations = newAssociations;
//		System.out.println("after reassigning assocations");listAssociations();//FIXME remove
		immobile.removeAll(immobile);
		immobile.addAll(newImmobile);
		    
		
	
    }
    public int[][] getRoots() {
	int[][] answer = new int[getNumberOfTerms()][group.getRank()];
	for( int i = 0; i < getNumberOfTerms(); i++)
	    answer[i] = get(i).getRoot();
	return answer;
    }
    public Set<String> getAllVariables() {
	Set<String> ans = new TreeSet<String>();
	for(Sunipotent s:product)
	    ans.addAll(s.getArgument().getAllVariables());
	return ans;
    }
    public static PrefixRootPair prefixRootPair(String x) {
	
	String[] pair = x.split("_\\{");

	if( pair.length != 2){
	    return null;
	}
	
	if( pair[1].indexOf("}") != pair[1].length()-1){
	    return null;
	}
	String tupleString = pair[1].substring(0,pair[1].length()-1);
	
	if(!Pattern.compile("\\-?\\d*").matcher(tupleString).matches()){
	    return null;
	}
	int[] root = edu.siu.math.egut.io.Algorithms.tupleFromString(tupleString);
	return new PrefixRootPair(pair[0], root);
    }
    public void stateNumberOfAssociations() {
	System.out.println( associations.size() + "associations.");
	
    }
  
}
